デッドロックに対処する 4 つの方法
warning.icon デッドロック が発生するのは稀で、発生した場合も影響が軽微であることが確実に分かっている場合のみ有効 2. デッドロックを検出する
warning.icon ただし、ランタイム がすべてのゴルーチンが待機していると判断した場合のみ検出し、panic を出す デッドロックを完全に検出する方法
グラフ循環の検出する方法としては、深さ優先探索 を応用したものがある 他の フレームワーク やランタイム、データベースシステムで採用されている 具体的には、走査 している間に訪れたノードを記録し、すでに訪問済みのノードに遭遇した場合は循環している デッドロックを検出後の処理
1. 動作できなくなった実行（ゴルーチン）を終了する
e.g. Go
2. リソースを要求している実行にエラーを返す
これにより、実行はエラーに応じてリソースを解放したり、一定時間後に再試行するなど何らかの後処理が行える
3. デッドロックを回避する
Banker's algorithm は、リソースの要求を許可するかどうかを決定するときに実行される
システムが「安全」な状態に維持される場合にのみリソースの要求を許可する
逆に「安全でない状態」に遷移する場合、リソースの要求を許可できる状態になるまで実行は一時停止される
ここでの「安全」とは、リソースの最大数を要求した場合でも、すべての実行が完了するようにスケジューリングされている ことを指す
= デッドロックを回避できる
逆に上記以外の場合は「安全ではない」
Banker's algorithm では、以下の情報を用いる
各実行が要求できるリソースの最大数
各実行が保持しているリソース
各リソースの利用可能数
warning.icon OS や言語の ランタイム では Banker's algorithm は使えない 各実行が要求できるリソースの最大数が必要だが、OS やランタイムが各 プロセス や スレッド が要求するリソースを事前に知ることはできないため e.g. プログラムがランタイムの途中でスレッドを作成し、それがどのようなリソースを使うかは、実行するまで分からない
また、 Banker's algorithm は 実行内のプロセス数が固定されている 前提で設計されているが、実際の OS では新しいプロセスやスレッドを頻繁に生成・終了したりするため
e.g. 固定数のセッションを持つデータベースのコネクションプール
https://scrapbox.io/files/67ca99a2da05429c59d92949.png
シナリオ A で実行 a がもう 1 つ別のリソースを要求して許可された場合、シナリオ B に移行する
シナリオ A は安全である
∵ すべての実行を完了できるスケジューリングが存在できるため
e.g.
https://scrapbox.io/files/67ca9b2235bbcda214cec1da.png
残りの 3 つのリソースをすべて実行 b に割り当てる
その間、実行 a と c がリソース要求した場合、「安全でない」状態に陥るため一時停止する
実行 b が完了してリソースを解放したら、そのリソースを実行 c に割り当てる
...
一方、シナリオ B は安全でない
∵ 2 つのリソースしか空きが無いが、実行 a ~ c はそれぞれ更に 5, 3, 5 のリソースを要求できるため
warning.icon 各ゴルーチンが必要とするのがどのリソースか分かっている場合、処理を簡略化できる
e.g. 送金システム
あるゴルーチンが送金元と先の口座をロックしようとする際に、その 2 つの口座のいずれかが他のゴルーチンに使われている場合は「安全でない」状態に陥るため一時停止する
4. デッドロックを防ぐ
ロックの逆転 が起きないようにすれば（ロックの順序が同じになれば）、デッドロックは起きない 事前に排他的リソースが分かっている場合
分かっていない場合
現在保持しているリソースよりも前の順序のリソースを獲得しないようにする
前の順序のリソースを獲得したい場合は、保持しているリソースを解放することで、再び要求する